#ifndef UTIL_H
#define UTIL_H

#include <iostream>

#include <boost/multiprecision/cpp_int.hpp>

namespace mpn = boost::multiprecision;

typedef float f32;
typedef double f64;
typedef char i8;
typedef short i16;
typedef int i32;

// #define byte unsigned char
typedef unsigned char byte;
typedef byte u8;
typedef unsigned short u16;
typedef unsigned int u32;

#ifdef __x86_64__

typedef long long i64;
typedef unsigned long long u64;

typedef __int128 i128;

#else

#endif

//是个闭区间 [minNum,maxNum]
size_t x_next_random(size_t minNum, size_t maxNum);

size_t x_next_random(size_t maxNum);

size_t x_gcd(size_t a, size_t b);

template<class T>
void xp(T t)
{
    std::cout << t << std::endl;
}

int mod(int a, int m);

int safe_mod(int a, int m);

// 扩展欧几里得算法（递归版）
// 返回 gcd(a, b)，并更新 x 和 y 使得 ax + by = gcd(a, b)
mpn::cpp_int extended_gcd(mpn::cpp_int a, mpn::cpp_int b, mpn::cpp_int &x, mpn::cpp_int &y);

// 计算模逆元（a^{-1} mod m）
mpn::cpp_int mod_inverse(mpn::cpp_int a, mpn::cpp_int m);

// 快速模幂计算 (a^b mod m)
mpn::cpp_int fast_mod_exp(mpn::cpp_int a, mpn::cpp_int b, mpn::cpp_int m);

#endif // UTIL_H
